package alo.p19;

/**
 * @ClassName MaxContinuousSum
 * @Description 最大连续子序列和
 * @Author Fanxc
 * @DATE 2021/3/15 14:36
 * @Version 1.0
 */
public class MaxContinuousSum {
    int maxContinuousSum(int[] A,int n){
        int[] M=new int[n];
        int maxSum=0;
        if (A[0]>0){
            M[0]=A[0];
        }else {
            M[0]=0;
        }
        for (int i = 1; i < n; i++) {
            if (M[i-1]+A[i]>0){
                M[i]=M[i-1]+A[i];
            }else {
                M[i]=0;
            }

        }
        for (int i = 0; i < n; i++) {
            if (M[i]>maxSum){
                maxSum=M[i];
            }
        }
        return maxSum;
    }

    int maxContinuousSum2(int[] A,int n){
        int sumSoFar=0,sumEndingHere=0;
        for (int i = 0; i < n; i++) {
            sumEndingHere=sumEndingHere+A[i];
            if (sumEndingHere<0){
                sumEndingHere=0;
                continue;
            }
            if (sumSoFar<sumEndingHere){
                sumSoFar=sumEndingHere;
            }
        }
        return sumSoFar;
    }

    int maxSumWithNoTwoNumrers(int[] A,int n){
        int[] M=new int[n+1];
        M[0]=A[0];
        M[1]=(A[0]>A[1]?A[0]:A[1]);
        for (int i = 2; i < n; i++) {
            M[i]=M[i-1]>M[i-2]?M[i-1]:M[i-2]+A[i];
        }
        return M[n-1];
    }
}
